#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

LinkList List_TailInsert(LinkList &L);
LinkList List_HeadInsert(LinkList &L);

int main() {}

// 尾插法建立单链表
// 时间复杂度 O(n)
LinkList List_TailInsert(LinkList &L)
{
    int x;
    L = (LinkList)malloc(sizeof(LNode)); // 头结点
    L->next = NULL;
    LNode *s, *r = L; // r为表尾指针
    scanf("%d", &x);
    while (x != 9999) // 输入9999表示结束
    {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        r->next = s; // r指向新的表尾结点
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL; // 尾结点指针置空
    return L;
}

//  利用头插法建立单链表
//  可以应用于链表的逆置(*****)
LinkList List_HeadInsert(LinkList &L)
{
    int x;
    LNode *s;
    L = (LinkList)malloc(sizeof(LNode)); // 头结点
    L->next = NULL;                      // 初始化空链表
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LinkList)malloc(sizeof(LNode));
        // 不理解可以自己画图
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}